
#include "swap.c"

#ifndef SORT_MERGE
#define SORT_MERGE

// 合并两个有序数组
void merge(ElementType a[], ElementType temp[], int leftStart, int rightStart, int rightEnd) {
    // 左边起点
    int left = leftStart;
    // 左边终点
    int leftEnd = rightStart - 1;
    // 右边起点
    int right = rightStart;
    // 临时数组的下标
    int tempIndex = leftStart;
    
    // 两个数组都有元素
    while (left <= leftEnd && right <= rightEnd) {
        if (comparator(a[left], a[right]) <= 0) {
            temp[tempIndex++] = a[left++];
        } else {
            temp[tempIndex++] = a[right++];
        }
    }
    // 左边有剩余
    while (left <= leftEnd) {
        temp[tempIndex++] = a[left++];
    }
    // 右边有剩余
    while (right <= rightEnd) {
        temp[tempIndex++] = a[right++];
    }
}

void merge_pass(ElementType a[], ElementType temp[], int length, int step) {
    int i;
    for (i=0; i < length - 2 * step; i += 2*step) {
        // 左边起点
        int leftStart = i;
        // 右边起点
        int rightStart = i + step;
        // 右边终点
        int rightEnd = i + 2*step - 1;
        // 合并
        merge(a, temp, leftStart, rightStart, rightEnd);
    }
    if (i + step < length) {
        // 归并最后2个子列
        merge(a, temp, i, i + step, length-1);
    } else {
        // 只剩下1个子列
        for (int j=i; j < length; j++) {
            temp[j] = a[j];
        }
    }
}

// 非递归实现的 merge 排序算法
void merge_Sort(ElementType a[], int length) {
    // 临时数组
    ElementType *temp = malloc(sizeof(ElementType) * length);
    // 从 1 到 length/2 为步长，两两合并
    for (int step=1; step < length; ) {
        merge_pass(a, temp, length, step);
        step *= 2;
        merge_pass(temp, a, length, step);
        step *= 2;
    }
    free(temp);
}

#endif
